package com.hh.hot100;

import java.util.HashMap;

/**
 * @Author hanghao
 * @Date 2023/6/26 13:41
 * @Version 1.0
 */

public class No128 {
    /**
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * 因为时间复杂度是O(n) 所以sort() 应该不可以用的
     * 本文一共会介绍四种思路，可按需食用。
     *     方法1 哈希集合（最普遍也最简单的思路，必须掌握）
     *     方法2 哈希表（思路1的进阶）
     *     方法3 动态规划（极其巧妙，推荐掌握）
     *     方法4 并查集（建议掌握）
     * 看到本题找最长连续序列，每个人都会想到两种最朴素的解法之一：
     * 1.先排序，从前往后找最长连续上升序列即可。该思路简单有效，但是复杂度已经至少有O(nlogn)O(nlogn)O(nlogn)。实现起来也比较简单，在此不讨论该解法。
     * 2.遍历数组中的每个元素num，然后以num为起点，每次+1向后遍历num+1,num+2,num+3...，判断这些元素是否存在于数组中。假设找到的最大的连续存在的元素为num+x，
     * 那么这个连续序列的长度即为x+1。最后将每个num所开始序列长度取个最大值即可。
     *

     */
    public static int longestConsecutive(int[] nums) {
        //方法一
//        HashSet<Integer> set = new HashSet<>();
//        for(Integer num : nums) {
//            set.add(num);
//        }
//        int res = 0;
//        for (Integer num : set) {
//            int cur = num;
//            if(!set.contains(cur - 1)) {
//                while(set.contains(cur + 1)) {
//                    cur++;
//                }
//            }
//            res = Math.max(res, cur - num + 1);
//        }
//        return res;
//        //方法二 改进
//        // key表示num，value表示num最远到达的连续右边界
//        HashMap<Integer, Integer> map = new HashMap<>();
//        for(int num : nums) {
//            map.put(num, num);
//        }
//        int res = 0;
//        for(int num : nums) {
//            if (!map.containsKey(num - 1)) {
//                int right = map.get(num);
//                //遍历得到最远的右边边界
//                while(map.containsKey(right + 1)) {
//                    right = map.get(right + 1);
//                }
//                map.put(num, right);
//                res =  Math.max(res, right - num + 1)
//            }
//
//        }
//        return res;
        //方法三 动态规划的方法
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for(int num : nums) {
            //当map中不包含num，也就是num第一次出现
            if(!map.containsKey(num)) {
                int left = map.getOrDefault(num - 1, 0);
                int right = map.getOrDefault(num + 1, 0);
                int curlen = left + right + 1;
                res = Math.max(res, curlen);
                map.put(num, -1);
                map.put(num - left, curlen);
                map.put(num + right,curlen);
            }
        }
        return res;

    }

    public static void main(String[] args) {
        int[] nums = new int[]{100,4,200,1,3,2};
        int i = longestConsecutive(nums);
        System.out.println(i);
    }

}
